package com.frx.sort.heap;

import java.util.Arrays;

/**
 * @author ：frx
 * @date ：Created in 2019/11/12 22:51
 * @description：ToDO
 * @modified By：
 * @version: ToDO
 */
public class TopK {

    public static void main(String[] args){

        int[] arr = {3,1,2,4,6,5,7};
        System.out.println(Arrays.toString(topK(arr,3)));
    }

    public static int[] topK(int[] arr,int k){
        int[] minHeap = new int[k];
        for (int i=0;i<k;i++){
            minHeap[i] = arr[i];
        }
        // 1.构建一个小顶堆
        buildHeap(minHeap);
        System.out.println(Arrays.toString(minHeap));
        for (int i=k;i<arr.length;i++){
            // 将数组中的元素与小顶堆依次比较，如果数组中的元素比小顶堆大，则将该元素赋值给小顶堆的堆顶，然后进行下沉
            if (arr[i] > minHeap[0]){
                minHeap[0] = arr[i];
                siftdown(minHeap,0,minHeap.length);
            }
        }
        return minHeap;
    }
    private static void buildHeap(int[] arr){
        int len = arr.length;
        for (int n = (len-1)/2;n>=0;n--){
            siftdown(arr,n,arr.length);
        }
    }
    private static void siftdown(int[] arr,int n,int len){
        while (true){
            int minIndex = n;
            if (2*n+1 < len && arr[2*n+1]<arr[n]){
                minIndex = 2*n+1;
            }
            if (2*n+2<len&& arr[2*n+2] < arr[minIndex]){
                minIndex = 2*n+2;
            }
            if (minIndex == n){
                break;
            }
            int tmp = arr[minIndex];
            arr[minIndex] = arr[n];
            arr[n] = tmp;
            n = minIndex;
        }
    }
}
